// https://leetcode.cn/problems/binary-tree-paths/

// 题干：给你一个二叉树的根节点 root，按任意顺序返回所有从根节点到叶子节点的路径。
//       叶子节点 是指没有子节点的节点。

// 示例：输入：root = [1,2,3,null,5]
//       输出：["1->2->5","1->3"]

// 碎语：只要有回溯，就会有恢复现场，只是简单题不太明显
//       而加了全局变量就要考虑这个问题
//       如果本题放到参数传进去，可以让函数来帮我们恢复现场
//       本题的精华就在于此

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
    vector<string> ret;
public:
    vector<string> binaryTreePaths(TreeNode* root)
    {
        string s;
        dfs(root, s);
        return ret;
    }

    void dfs(TreeNode* root, string path)
    {
        if (root == nullptr) return ;

        if (root->left == nullptr && root->right == nullptr){
            path += to_string(root->val);
            ret.push_back(path);
            return ;
        }

        path += to_string(root->val);
        path += "->";

        dfs(root->left, path);
        dfs(root->right, path);
    }
};

int main()
{
    Solution sol;

    auto root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);

    vector<string> index = sol.binaryTreePaths(root);
    for (const auto& str : index){
        cout << str << endl;
    }

    return 0;
}